/**
 * 
 */
package com.hermeneute.sa;

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.Iterator;

import com.sun.xml.internal.bind.v2.schemagen.xmlschema.TopLevelAttribute;

/**
 * @author Mauceri
 * 
 * From the paper "Replacing suffix trees with enhanced suffix arrays"
 *
 */
public class EnhancedSuffixArray {

	//class interval
	class Interval {
		Integer lcp;
		Integer lb;
		Integer rb;
		Interval() {
			lcp = 0;
			lb = 0;
			rb = null;
		}

		Interval(Integer lcp, Integer lb, Integer rb) {
			this.lcp = lcp;
			this.lb = lb;
			this.rb = rb;
		}
		
		void print() {
			System.out.println(lcp+"-["+lb+".."+rb+"]");
		}
	}
	
	//stack cell
	class Cell {
		Interval interval;
		ArrayList<Interval> childList;
		int pos = -1;
		Cell() {
			interval = new Interval();
			childList = null;
		}

		Cell(Integer lcp, Integer lb, Integer rb, ArrayList<Interval> childList) {
			interval = new Interval(lcp, lb, rb);
			this.childList = childList;
		}
	}
	
	//stack
	class StackOfIntervals {
		ArrayList<Cell> stack = new ArrayList<Cell>();
		public StackOfIntervals() {
		}
		
		public void push(Cell c) {
			stack.add(c);
		}

		public void push(Integer lcp, Integer lb, Integer rb, ArrayList<Interval> childList) {
			stack.add(new Cell(lcp,lb,rb,childList));
		}

		public Cell pop() {
			if (stack.isEmpty())
				throw new EmptyStackException();
			return stack.remove(stack.size()-1);
		}

		public boolean isEmpty() {
			return stack.isEmpty();
		}
		
		Cell top() {
			return stack.get(stack.size()-1);
		}
		
		void printTop() {
			System.out.println("{"+top().interval.lcp+" "+top().interval.lb+" "+top().interval.lcp+" "+top().childList.size()+"}");
		}
	}
	
	public SuffixArray sa = null;
	BufferedWriter out = null;

	EnhancedSuffixArray() {
		
	}
	/*
	 * The Algorithm Traverse and Process the lcp-interval tree
	 * as described in the referenced paper
	 * 
	 * lastInterval := null
	 * push(0, 0,null, [ ])
	 * for i := 1 to n do
	 * 	lb := i - 1
	 * 	while lcptab[i] < top.lcp
	 * 		top.rb := i - 1
	 * 		lastInterval := pop
	 * 		process(lastInterval)
	 * 		lb := lastInterval.lb
	 * 		if lcptab[i] <= top.lcp then
	 * 			top.childList := add(top.childList, lastInterval)
	 * 			lastInterval := null 
	 * 	if lcptab[i] > top.lcp then
	 * 		if lastInterval !=null then
	 * 			push(lcptab[i], lb,null, [lastInterval])
	 * 			lastInterval := null 
	 * 		else 
	 * 			push(lcptab[i], lb,null, [ ])
	 */
	
	void process (Interval intv, ArrayList<Interval> cl) {
		intv.print();
		for (Iterator<Interval> it = cl.iterator(); it.hasNext();) {
			Interval intvc = it.next();
			System.out.print("       ");intvc.print();
		}
	}
	
	public void traverseLcpIntervalTree () {
		StackOfIntervals s = new StackOfIntervals();
		Interval lastInterval = null;
		//sa.printTables();
		int n = sa.sa.length;
		Integer lb;
		
		s.push(0,0,null,new ArrayList<Interval>());
		for (int i = 1; i < n ; i++) {
			lb = i - 1;
			while (sa.lcp[i] < s.top().interval.lcp) {
				s.top().interval.rb = i-1;
				lastInterval = s.pop().interval;
				process(lastInterval,s.top().childList);
				lb = lastInterval.lb;
				if (sa.lcp[i] <= s.top().interval.lcp) {
					s.top().childList.add(lastInterval);
					lastInterval = null;
				}
			}
			if (sa.lcp[i] > s.top().interval.lcp) {
				ArrayList<Interval> cl = new ArrayList<Interval>();
				if (lastInterval != null) {
					cl.add(lastInterval);
					s.push(sa.lcp[i],lb,null,cl);
					lastInterval = null;
				} else {
					s.push(sa.lcp[i],lb,null,cl);					
				}
			}
		}
	}
	
	static String file2String(String fileName) {
		File f = new File(fileName); 
		FileInputStream fis;
		BufferedReader in  = null;
		String txt = "";

		try {
			fis = new FileInputStream(f);
			 InputStreamReader isr = new InputStreamReader(fis);
			in = new BufferedReader(isr);
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} 
		
		try { 
			String line = null;
			while ( (line = in.readLine()) != null ) { 
				txt += " "+line;
			} 

		} catch (IOException e) { 
			e.printStackTrace();
		} 
		return txt;
	}
	
	
	// Result's file
	public void closeResults() {
		try {
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	public void openResult(String fileName) {
		File f = new File(fileName); 
		FileOutputStream fos;
		String txt = "";

		try {
			fos = new FileOutputStream(f);
			 OutputStreamWriter osr = new OutputStreamWriter(fos);
			out = new BufferedWriter(osr);
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} 
	}

	
	public static void main (String [] args) {
		String v1  = "acaaacatatz";
		String v2 = "abracadabra";
		String v = "mississippi";
		String v4  = "aaaaaaaaaaaaaaaaaaaaaaaaaaa";
		String text = "C:\\Documents and Settings\\Administrator\\Desktop\\HeartOfDarkness.txt";
		String results = "C:\\Documents and Settings\\Administrator\\Desktop\\HeartOfDarknessRes.txt";

		v = file2String(text);
		SuffixArray sa = new SuffixArray(v);
		sa.d = 2;
		sa.init();
		sa.getsa();
		sa.cleanup();
		sa.lcp();
		sa.sa2bwt();
		//EnhancedSuffixArray esa = new EnhancedSuffixArray();
		//esa.sa = sa;
		//esa.traverseLcpIntervalTree();
		EnhancedSuffixArray esa1 = new EnhancedSuffixArray() {

			/* (non-Javadoc)
			 * @see com.hermeneute.sa.EnhancedSuffixArray#process(com.hermeneute.sa.EnhancedSuffixArray.Interval, java.util.ArrayList)
			 */
			@Override
			void process(Interval intv, ArrayList<Interval> cl) {
				boolean localMaximal = true;
				boolean superMaximal = true;
				StringBuffer res = new StringBuffer();
				
				for (int i = intv.lb+1; i <= intv.rb;i++) {
					if(sa.lcp[i] != intv.lcp) {
						localMaximal = false;
						break;
					}
				}
				if(localMaximal){
					for (int i = intv.lb; i <= intv.rb;i++) {
						for (int j = intv.lb; i <= intv.rb;i++) {
							if(i != j && sa.bwt[i] == sa.bwt[j]) {
								superMaximal = false;
								break;
							}
						}
					}
				} else {
					superMaximal = false; 
				}
				if (superMaximal) {
					try {
						int size = intv.rb-intv.lb+1;
						out.write(size+" ");
						out.write(sa.txt.substring(sa.sa[intv.lb],sa.sa[intv.lb]+intv.lcp));
						out.newLine();
						out.flush();
					} catch (IOException e) {
						e.printStackTrace();
					}
				}
			}
		};
		esa1.sa = sa;
		esa1.openResult(results);
		esa1.traverseLcpIntervalTree();
		esa1.closeResults();
		System.out.println("end");
	}

}
